// FRAOZO - Project 6a

#include <iostream>
#include <limits.h>
#include "d_except.h"
#include <list>
#include <fstream>
#include "d_matrix.h"
#include "graph.h"
#include <queue>
#include <vector>

//Used for getNeighbors - will return all neighbors, even
//   if they are visited
#define ALLNEIGHBORS true

using namespace std;


vector<int> getNeighbors(const graph &g, int nodeId, 
                         bool onlyVisited = true)
//return a vector of all neighbors of node nodeId
// if countVisited is true, do not include visited neighbors
{
   vector<int> neighbors;
   
   //foreach node in the graph
   for (int candidate=0; candidate<g.numNodes(); candidate++)
   {
      if (candidate == nodeId)
	 continue;
      
      if (onlyVisited)
      {
      	 if (g.isEdge(nodeId, candidate) && !g.isVisited(candidate))
	    neighbors.push_back(candidate);
      }
      else 
      {
	 if (g.isEdge(nodeId, candidate))
	    neighbors.push_back(candidate);
      }
   }

   return neighbors;
} // end getNeighbors

void createEdge (graph &orig, graph &sf, int node)
//Recursively create edges (in sf) between unvisited nodes
// (in the original graph) until no neighboring nodes are visited
//See findSpanningForest
{
   //visit the node
   orig.visit(node);
   vector<int> unVisNeighbors = getNeighbors(orig, node);

   
   //base case - no unvisited neighbors
   if (unVisNeighbors.size() == 0)
      return;

   int neighbor = unVisNeighbors[0];

   //create a bidi edge
   int weight1 = orig.getEdgeWeight(node, neighbor);
   int weight2 = orig.getEdgeWeight(neighbor, node);
   sf.addEdge(node, neighbor, weight1);
   sf.addEdge(neighbor, node, weight2);

   createEdge(orig, sf, neighbor);
   
} // end createEdge

void traverseGraph(graph &g, int startNode)
//From the startnode, visit every neighbor until there are
// no unvisited neighbors
{
   g.visit(startNode);
   
   vector<int> neighbors = getNeighbors(g, startNode);

   //base case - no unvisited neighbors
   if (neighbors.size() == 0)
      return;

   //foreach unvisited neighbor
   for (int idx=0; idx<neighbors.size(); idx++)
   {
      int neighbor = neighbors[idx];
      traverseGraph(g, neighbor);
   }
   
} // end traverseGraph

bool hasCycle(graph &g, int currentNode, int prevNode = 0)
//Called recursively.  If a neighbor of currentNode is already visited
//  and is not the prevNode, g contains a cycle
{
   g.visit(currentNode);
   
   //get ALL neighbors - even if they are visited (hence false)
   vector<int> neighbors = getNeighbors(g, currentNode, ALLNEIGHBORS);

   for (int idx=0; idx<neighbors.size(); idx++)
   {
      int neighbor = neighbors[idx];

      //Skip the node that we came from
      if (neighbor == prevNode)
	 continue;

      //base case - one of the neighbors is visited, 
      // and is not the prevNode
      if (g.isVisited(neighbor))
	 return true;

      //Recurse.  If true, unwind.  Note that the currentNode 
      //   will become the prevNode, and the neighbor will
      //   become the currentNode
      if (hasCycle(g, neighbor, currentNode))
	 return true;
   }

   return false;
} // end hasCycle

bool isCyclic(graph &g)
// Returns true if the graph g contains a cycle.  Otherwise, returns false.
{
   //foreach unvisited node,
   for (int node=0; node<g.numNodes(); node++)
      if (!g.isVisited(node))
	 if (hasCycle(g, node))
	 {
	    g.clearVisit();
	    return true;
	 }

   g.clearVisit();
   return false;
} // end isCyclic


void findSpanningForest(graph &g, graph &sf)
// Create a graph sf that contains a spanning forest on the graph g.  
{
   //foreach unvisited node, start a recursive createEdge routine
   for (int node=0; node<g.numNodes(); node++)
      if (!sf.isVisited(node))
	 createEdge(g, sf, node);

   g.clearVisit();
   sf.clearVisit();

} // end findSpanningForest

bool isConnected(graph &g)
// Returns true if the graph g is connected.  Otherwise returns false.
{
   int startNode = 0;
   traverseGraph(g, startNode);
   bool returnVal = g.allNodesVisited();
   g.clearVisit();
   return returnVal;
} // end isConnected


int main(int argc, char* argv[])
{
   char x;
   ifstream fin;
   string fileName;
   
   // Read the name of the graph from the keyboard or
   // hard code it here for testing.
   
   fileName = (argc == 2) ? argv[1] : "graph1.txt";

   fin.open(fileName.c_str());
   if (!fin)
   {
      cerr << "Cannot open " << fileName << endl;
      return 1;
   }

   try

   {
      cout << "Reading graph" << endl;
      graph g(fin);
      cout << g;

      bool connected;
      bool cyclic;

       connected = isConnected(g);
      cyclic = isCyclic(g);

      if (connected)
	 cout << "Graph is connected" << endl;
      else
	 cout << "Graph is not connected" << endl;

      if (cyclic)
	 cout << "Graph contains a cycle" << endl;
      else
	 cout << "Graph does not contain a cycle" << endl;

      cout << endl;
     
      cout << "Finding spanning forest" << endl;

      // Initialize an empty graph to contain the spanning forest
      graph sf(g.numNodes());
      findSpanningForest(g,sf);

      cout << sf;

      cout << "Spanning forest weight: " << sf.getTotalEdgeWeight()/2 << endl;

       connected = isConnected(sf);
      cyclic = isCyclic(sf);

      if (connected)
	 cout << "Graph is connected" << endl;
      else
	 cout << "Graph is not connected" << endl;

      if (cyclic)
	 cout << "Graph contains a cycle" << endl;
      else
	 cout << "Graph does not contain a cycle" << endl;

      cout << endl;

    }    
   catch (indexRangeError &ex) 
   { 
      cout << ex.what() << endl; return 1;
   }
   catch (rangeError &ex)
   {
      cout << ex.what() << endl; return 1;
   }
}

